package Ali;

import java.util.Arrays;

/**
 * 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
 *
 * 要求时间复杂度为O(n)。
 * @author le
 */
public class Test05
{
    public static void main(String[] args)
    {
        int[] num = {-2,1,-3,4,-1,2,1,-5,4};

        /**
         * dp[i] = dp[i-1] + num[i]
         */
        int[] dp = new int[num.length];
        dp[0] = num[0];
        for (int i = 1;i < num.length;i++){
            if (dp[i-1] <= 0){
                dp[i] = num[i];
            }else{
                dp[i] = dp[i-1]+num[i];
            }


        }
        Arrays.sort(dp);
        System.out.println(dp[dp.length-1]);
    }
}
